package a14_Sort;

/**
 * @Author quan
 * @Description 希尔排序：不稳定
 * @Date 2023/4/27 10:20
 */
public class heirSort {
    public static void main(String[] args) {
        int[] arr = {1,56,23,12,4,12,9,6,8,17};
        heirSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
    //先不断按照gap分组，让gap不断/=2或者/=3，最后当gap=1时使用直接插入排序即可。
    public static void heirSort(int[] arr){
        // gap/2
        int gap = arr.length >> 1;
        while (gap > 1){
            insetSortByGap(arr,gap);
            gap = gap >> 1;
        }
        //此时gap为1，直接使用插入排序
        insetSortByGap(arr,1);
    }
    //对每次分组的子数组进行排序
    private static void insetSortByGap(int[] arr, int gap) {
        //j原来是向前看一个单位，现在是向前看gap个单位
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j-gap > 0 ; j=j-gap) {
                if(arr[j] < arr[j-gap]){
                    swap(arr,j,j-gap);
                }
            }
        }
    }
    //交换函数
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
